`
https://leetcode.cn/problems/edit-distance/
`

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  const m = word1.length, n = word2.length
  // 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i+1][j+1]
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))

  // 第一行和第一列就是下标值，因为有几个字符就插入几次
  // 处理行
  for (let i = 0; i <= n; i++) {
    dp[0][i] = i
  }
  // 处理列
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // 相同的跳过
      // 由于创建的 dp 多了一行一列，所以跟原字符串的下标有一格的偏差
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else {
        dp[i][j] = Math.min(
          // 插入
          // 在 word1[i] 处插入和 word2[j] 相同的字符
          // 那么word2[j] 就被匹配了，前移 j，继续和 i 对比
          dp[i][j - 1] + 1,
          // 删除
          // 将 word1[i] 处的字符删掉
          // 前移 i ，继续和 j 对比
          dp[i - 1][j] + 1,
          // 替换
          // 直接把 word1[i] 替换成 word2[j]，这样它俩就匹配了
          // 同时前移 i，j 继续对比
          dp[i - 1][j - 1] + 1
        )
      }
    }
  }

  return dp[m][n]
};